package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/1/7
 */
public class BuildTree {

    public static void main(String[] args) {
        TreeNode ret = buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(ret);
    }

    static int pL = 0;

    static Map<Integer, Integer> INDEX_CACHE = new HashMap<>();

    public static TreeNode buildTree(int[] preOrder, int[] inOrder) {
        for (int i = 0; i < inOrder.length; i++) {
            INDEX_CACHE.put(inOrder[i], i);
        }
        return buildTree(preOrder, inOrder, 0, inOrder.length - 1);
    }

    public static TreeNode buildTree(int[] preOrder, int[] inOrder, int iL, int iR) {
        if ( pL < preOrder.length && iL <= iR ) {
            TreeNode ret = new TreeNode(preOrder[pL++]);
            Integer m = INDEX_CACHE.get(ret.val);
            if ( m != null ) {
                ret.left = buildTree(preOrder, inOrder, iL, m - 1);
                ret.right = buildTree(preOrder, inOrder, m + 1, iR);
            }
            return ret;
        }
        return null;
    }

}
